java算法

您所在的位置：网站首页 › 二分查找算法 java › java算法

java算法

2024-07-14 11:25| 来源: 网络整理| 查看: 265

三、二分查找优缺点

优点是比较次数少，查找速度快，平均性能好；

其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

使用条件：查找序列是顺序结构，有序。

四、代码实现

1.非递归方法

private static int binarySearch(int[] arr, int key) { int left = 0; int right = arr.length-1; int mid ; if (key < arr[left] || key > arr[right] || left > right){ return -1; } while(left < right){ mid = (left + right)/2; if (arr[mid] < key){ left = mid +1; }else if(arr[mid] > key){ right = mid - 1; }else { return mid ; } } return -1; }

2.递归方法

public static int binarySearch(int[] arr,int left,int right,int key){ if (key < arr[left] || key > arr[right] || left > right){ return -1; } int mid = (left+right)/2; if (arr[mid]key){ return binarySearch(arr,left,mid-1,key); }else { return mid; } }

五、时间复杂度和空间复杂度

时间复杂度采用的是分治策略

最坏的情况下两种方式时间复杂度一样：O(log2 N)

最好情况下为O（1）

空间复杂度算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数

非递归方式：由于辅助空间是常数级别的，所以空间复杂度是O(1);

递归方式：递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的：空间复杂度：O(log2N )

【本文地址】

java算法

java算法

今日新闻

推荐新闻